.ASEC(History of the BEINGS Representation of Knowledge)


This appendix introduces the reader to the concept of organizing knowledge
as similarly-structured modules, called BEINGs. It should be skipped by those
familiar with that construction. For a more thorough treatment,
read either:

.BN

Section 4.6 of Green et al.,
⊗4Progress Report on Program-Understanding Systems⊗*, Memo AIM-240,
CS Report STAN-CS-74-444, Artificial Intelligence Laboratory, Stanford
University, August, 1974; or 

Lenat, ⊗4BEINGS: Knowledge as
Interacting Experts⊗*, 4th IJCAI, 1975,
or 

Lenat, ⊗4Synthesis of Large Programs from Specific Dialogues⊗*,
3rd World Conference on Cybernetics and Systems, Roumania, 1975.

.E


.ASSEC(BEINGs and Experts)

Consider an interdisciplinary enterprise, attempted by a community of human
experts who are specialists in -- and only in -- their own fields.  What modes of 
i⎇teractions will be productive?  The dominant paradigm might well settle into
⊗4questioning and answering⊗* each other.
Instead of a chairman, suppose the group adopts rules for
gaining the floor, what a speaker may do,  and how to resolve disputes.
When a topic is being considered, one or two
experts might recognize it and speak up. In the course of their exposition
they might need to call on other specialists. This might be by name, by specialty,
or simply by posing a new sub-question and hoping someone could recognize his own
relevance and volunteer a suggestion.
If the task is to construct something, then the
activities of the experts should not be strictly verbal.  Often, one will 
recognize his relevance to the current situation and ask to ⊗4do⊗* something:
clarify or modify or (rarely) create.

What would it mean to ⊗4simulate⊗* the above activity?  Imagine several little 
programs, each one modelling a different expert. What should each program,
called a ⊗4BEING⊗*, be capable of?  It must possess a corpus of specific facts and
strategies for its designated speciality. It must interact via questioning and
answering other BEINGs. Each BEING should be able to recognize when it is relevant.
It must set up and alter structures, just as the human specialists do.

Let us return to our meeting of human experts.
To be more concrete, suppose their task is to design and code a large
computer program: a concept formation system[Hempel]. Experts who will be useful
include scientific programmers, non-programming psychologists,
system hackers, and management personnel.
Within each of these four major families will be many individual specialists.
What happens in the ensuing session?  When an expert participates, he will
either be aiding a colleague in some difficulty
or else transferring a tiny, customized 
bit of his expertise (facts about his field) into a programmed function
which can do something.  The final code reflects the members' knowledge,
in that sense.
Of course, experts within the same family will be able to communicate things
among themselves which are unintelligible to outsiders (e.g., when the hackers
start arguing about how to patch the system bugs that appear). 
Nevertheless, if we press him,
any of these specialists could transform his compressed jargon into a more universal
message (losing some information and some efficency), 
by giving examples and analogies, perhaps.

Suppose the project sponsor is quasi-active, submitting an initial specification
order for
the program, and then participating in the work as a (somewhat priveleged) member
of the team. This individual is the one who wants the final product, hence will be
called the ⊗4user⊗*.

How could BEINGs do all this? 
There would be some little program containing information
about ⊗7CONCEPT-FORMATION⊗*
(much more than would be used in writing any single concept formation program),
another BEING who knows
how to manage a group to
⊗7WRITE-PROGRAMS⊗*, and many lower-level specialists, for example 
⊗7INFO-OBTAINER, TEST, MODIFY-DATA-STRUCTURE, UNTIL-LOOP, 
VISUAL-PERCEPTION, AVOID-CONTRADICTION, PROPOSE-PLAUSIBLE-NAME⊗*.
Like the human specialists,
the BEINGs would contain far too much information, far too
inefficiently represented, to be able to say "we ourselves constitute
the desired program!"
They would have to discuss, and perhaps carry out, the concept formation task. They
would write specialized versions of themselves, programs which could do exactly what
the BEINGs did to carry out the task, no more nor less (although they would
hopefully take much less time, be more customized).
Some BEINGs 
(e.g., ⊗7TEST⊗*) may have several
distinct, streamlined fractions of themselves in the final program. BEINGs which
only aided other BEINGs (e.g., ⊗7PROPOSE-PLAUSIBLE-NAME⊗*)
may not have ⊗4any⊗* new correlates in the 
synthesized code.

An experimental system, PUP6, was designed and partially implemented. PUP6
synthesized a concept formation program (similar to Winston's), 
but the user, who is human,  must 
come up with certain specific answers to some of the BEINGs' critical queries.
A grammatical inference program and a  simple property list maintenance routine
were also generated. Only
a few new BEINGs had to be added to PUP6's orginal pool of 100
BEINGs in order to synthesize them, but communication
flexibility problems existed.
The choice of mathematics as the domain for the proposed system was made partially
to alleviate this problem.


.ASSEC(Internal Design of BEINGs)

Now that we have developed our "external specifications" for what the 
BEINGs must do, how
exactly will they do it?  Have we merely pushed the problem of Artificial
Intelligence down into the coding of the BEINGs?  Perhaps not, for we still have
our analogy to the interacting experts. Let us carry it further, analyze
synergetic cooperation among the humans, then try to model that in our
internal design of BEINGs.

Viewing the group of experts as a single entity, what makes it
productive? The members must be very different in abilities, in order to handle
a complex task, yet similar in basic cognitive structure 
(in the anatomy of their minds) to
permit facile communications to flow.
For example, each psychologist knows how to direct a programmer to do
some of the things he can do, but the specific facts he has tucked away
under this category must be quite unique. Similarly, each expert may have
a set of strategies for
recognizing his own relevance to a
proposed question, but the ⊗4contents⊗* of that knowledge varies from
individual to individual.  The proposed hypothesis is that all the experts can be
said to consist of categorized information, where the set of 
categories is fairly standard, and indicates the ⊗4types⊗* of questions
any expert can be expected to answer. An expert is considered ⊗4equivalent⊗*
to his answers to several standard questions.
Each expert has the same mental "parts", it
is only the values stored in these parts, their contents,
which distinguish him as an individual. 
The particular set of questions he can deal with is fixed, depending on which family
the expert belongs to. There is much -- but not total -- overlap between what two
humans from different professions can meaningly answer.

Armed with this dubious view of intelligence, let us return to the design of
BEINGs. Each BEING shall have many parts, each possessing a name (a question it
can deal with) and a value (a procedure capable of answering that question).
Henceforth, "⊗4part⊗*" will be used in this technical sense.
When a BEING asks a question, it is really just one
part who is asking. In fact, it must be that the ⊗4value⊗* subpart of some part
can't answer ⊗4his⊗* question without further assistance. He may not know
enough to call on specific other
BEINGs (in which case he broadcasts his plea, lettting anyone 
respond who feels relevant), but
he should ⊗4always⊗* specify what BEING ⊗4part⊗* the question should be answered by.
By analogy with the experts, each BEING in the same family 
will have the same fixed 
set of types of parts (will answer the same kinds of queries), and this uniformity 
should permit painless intercommunication
between specialists in the same profession.  Many of these parts will be common to
more than one family (e.g., "How long-winded are you").

Since the paradigm of
the meeting is questioning and anwwering, the names of the parts should
cover all the types of questions one expert wants to ask another. Each part of
each BEING will have implicit access to this list: it may ask only these
types of questions. Each BEING should ⊗4not⊗* have access to the list of all
BEINGs in the system: requests should be phrased in terms of what is wanted;
rarely is the name of the answerer specified in advance.
(By analogy: the human speaker is not aware of precisely who is in the room;
when he feels inadequate, he asks for help and hopes someone responds).

Once again: the concept of a system of BEINGs is that many entities coexist, 
clumped into a few major family groupings. Each individual BEING has
a complex structure, but that structure does not vary much from BEING to BEING;
it does not vary at all among BEINGs of the same family.
This idea has analogues in many fields: transactional analysis in
psychology, anatomy in medicine, modular design in architechture.

To carry out these ideas, we build a system of BEINGs, a modular program
which will interact with a human user and go through the same conversations,
and arrive at the same end products, that our human experts would.
Recasting the idea into operational terms, we arrive at this procedure for
writing a pool of BEINGs: 

.BN



λλ  Study the task which the pool is to do. See
what kinds of questions are asked by simulated experts, and notice how the experts
divide into a few major families α{f↓iα⎇.
The total number of families is important: if there are too many, it is hard for
specialized communication to occur; if too few families, many BEINGs will be forced
to answer questions they consider irrelevant.

λλ  Distill the corpus of collected communications into
a core of simple questions, Q↓f, for each family f,
in such a way that each inter-expert question or transfer
of control can be rephrased in terms of these Q's.
The sizes of the sets Q are very important.
If a Q is huge, addition of new
BEINGs will demand either great effort or great intelligence (an example of a
system like this is ACTORS). If a Q is too small, all the non-uniformity is simply
pushed down into the values of one or two general 
catchall questions (all first-order
logical languages do this). 

λλ  List all the BEINGs who will be
present in the pool, by family, and fill in their parts. 
The time to encode knowledge into many simple representation schemes is
proportional to the square of (occasionally exponential in) 
the amount of interrelated knowledge (e.g., consider the frame problem).
The filling in of a new BEING is  ⊗4independent⊗* of
the number of BEINGs already in the pool, because BEINGs can communicate
via nondeterministic goal mechanisms, and not have to know the names of the BEINGs
who will answer their queries. This filling in is  of course linear in the number of
questions a BEING must answer (e.g., the maximum size of any Q↓f).

λλ  The human user interacts with the completed
BEING community, until the desired task is complete.

.E

.ASSEC(BEINGs Interacting)

We now have some idea of what the internal structure of BEINGs are, but how do they
meet the external specifications we set for them: the reproduction of the human
experts' conversations and finished products?  The question is that of control in
the system, and it splits into two parts: how does the "right" BEING gain control,
and what does he "do" when he gets control?

The scenario, in PUP6, runs as follows. 
When control is about to be passed, the relinquisher
will specify a set of possible recipients (successors). 
Two extreme but common cases are
a singleton (he knows who should go next) and the set of all BEINGs (he has no
idea whatsoever).  Each possible candidate for control is asked if he is relevant
to the current situation.(If a goal is currently set forth, his EFFECTS part will
be asked if this guy can bring about that goal; if an unintelligible piece of
information is sitting around somewhere, his IDENTIFY part will be asked if this
guy can recognize that piece of info.) If more than one BEING replies that it feels
relevant, then their WHEN components are asked ⊗4how⊗* relevant they are right now.
If a tie still exists, their COMPLEXITY components are asked to decide which will be
faster, surer, lead to auxilliary desired effects, etc.
There will always be ⊗4some⊗* BEING who will take over;
the general management
types of BEINGs are always able  -- but reluctant  -- to do so. 

Once in control, a BEING B picks one of its parts, evaluates it, and repeats this
process until it decides to relinquish control. At that time, it puts forth a
list of possible successors.
For example, the ARGS
part might be first; if it asks for some arguments which no BEING has 
supplied, then the whole BEING might decide to fail. Some  parts, when evaluated,
might create a new BEING, might ask questions which require this whole process
to repeat recursively, etc. 
This "asking" really means broadcasting a request to one or two parts of
some other BEINGs (often every other BEING); 
for example "Is there a known fast way of gronking toves?" would
be asked as a search for a BEING whose COMPLEXITY indicated speed, and whose
EFFECTS part contained a production with a template matching "gronking toves".
A list of the responders would be returned. 
The questioner might pose some
new questions directly to these BEINGs, might turn control over to them directly,
might simply want to know that some exist, etc.

How does each BEING decide which parts to evaluate, and in which order,
once it gains control?
For our humans, the answer is: a combination of individual intelligence, the
training inherent in the family of expert you are, and universally accepted
constraints (common sense). For our BEINGs, we postulate a part called
ORDERING; each BEING consults its own Ordering part, the Ordering part
for its Family, and the universal Ordering Archetypical BEING. They 
partially constrain what part must be evaluated before what other part.
This appears to be difficult or tedious for whoever writes
BEINGs, since it might vary from BEING to BEING. In fact,
it rarely does vary, and most of the necessary constraints can be learned by
the system as it runs, and inserted into the proper slots.

Reexamine the question:
"What parts are evaluated, and in what order, when a particular
BEING gains control?" This decision depends primarily on the ⊗4types⊗* of parts
present in the BEING, not on their ⊗4values⊗*.  But every BEING in a family 
has the same
anatomy, so one single algorithm,
located in that family's Ordering part,
can assemble any BEING's parts into an executable
LISP function. Moreover, this assemby can be done when the system is first
loaded (or when a new BEING is first created), and need only be redone for a
BEING when the values of its parts change. Such changes are rare: experts are
not often open-minded. Thus the family's BEINGs can be compiled into executable
LISP functions.

.ASSEC(Aspects of BEINGs Systems)

It would be aesthetically pleasing to postulate that the only entities which exist
are BEINGs. Since this would require BEINGs' parts to be BEINGs, hence have parts of
their own, etc., an explosive recurrence would occur.  To avoid this, we set a slightly
different tack. Suppose that each part which has the same name must also have the same
internal structure. The format for part P is stored in the Representation part of the
archetypical BEING named P. The only allowable formats are the following:
an opaque executable expression, a pointer to some BEING or some specific part of a
BEING, a list of executable forms and pointers to BEINGs. Notice that there are
only three, and that they are all quite simple.

We shall demand that BEINGs write only new BEINGs, never any new functions,
production systems, etc. The humans often succeeded by distilling a tiny
specialization of their expertise; the BEINGs work similarly. 
In the process of discovery, this splitting occurs usually when some subpart is more
interesting than the whole.
In the process of automatic code-writing, this creation occurred when a BEING knew
how to write a fast, short, specialized, streamlined version of itself which was
capable of executing some specific subprocess used in the final "target" concept
formation program.


To clarify what BEINGs are and are not, they are contrasted with some other ideas. 
BEINGs linearly but
inefficently subsume such constructions as demons, functions, and assertions in an
associative data base
(in the earlier papers, brief demonstrations were provided).
FRAMES are sufficiently amorphous to subsume BEINGs. In philosophy,
FRAMES are meant to model perception, and intentionally rely on implicit
default values; BEINGs avoid making decisions without full awareness of the 
justification. 
This is also the difference  between HACKER and PUP6, the first experimental pool of
BEINGs. 
Since PUP6 wrote structured programs, it should be distinguished from macro
expansion. Macro procedures expand mechanically:
@2expand(sequence   m↓1  m↓2) = (sequence  
expand(m↓1)  expand(m↓2)))⊗*. BEINGs could use
information gleaned during expansion of m↓1 to improve the way m↓2 was handled.
ACTORs, unlike BEINGs, have no fixed structure imposed, and do not broadcast
their messages (they  specify who gets each message, by name, to a bureaucracy).


The performance of the BEINGs representation itself in PUP6 is mixed.
Two advantages were hoped for by using a uniform set of BEING parts.
Addition of new BEINGs to the pool was not easy (for untrained users)
but communication among
BEINGs ⊗4was⊗* easy (fast, natural). Two
advantages were hoped for by keeping the BEINGs highly structured.
The interactions (especially with the user) were
brittle, but
the complex tasks put to the system ⊗4were⊗* successfully completed.

The crippling problems are seen to be with user-system communication,
not with the BEINGs ideas themselves.
Sophisticated, bug-free programs ⊗4were⊗* generated, after hours of fairly high
level dialogue with an active user, after tens of thousands of messages passed
among the BEINGs.
Part of this success is attributed to distributing
the responsibility for writing code and for recognizing relevance, to a hundred
entities, rather than having a few central monitors worry about everything.
The standardization of parts made filling in the BEINGs' contents fairly painless,
both for the author and for BEINGs who had to write new BEINGs.

All this suggests two possible continuations, both of which are underway here
at the Stanford AI Lab. One is to
rethink the communication problems,
and develop a new system for the
concept formation program synthesis task. The earliest programs by our Automatic
Programming group had the goal "synthesize the target program somehow";
the later PUP1-6 research insisted on "getting the
target program by going through one ⊗4proper⊗* sequence of reasoning steps"; 
the group's proposed continuation wants several
untrained users to  succeed by many different "proper" routes.

This document is proposes an alternative direction for research effort.
This other way of continuing
is to find a task where BEINGs are well-suited, where
the problems encountered in PUP6 won't recur. What ⊗4are⊗* BEINGs good for?
The idea of a fixed set of parts (which distinguishes them from ACTORs) is
useful if the mass of knowledge is 
too huge for one individual to keep "on top" of.
It then should be organized in a
very uniform way (to simplify preparing it for storage), 
yet it must also be highly structured
(to speed up retrieval). 
A final ideal would be to find a domain where slightly-trained users could work
naturally, without (them ⊗4or⊗* us) having to battle the staggering complexities
of natural language handling. 
For these reasons, the author has chosen ⊗4fundamental mathematics⊗* 
as a task domain.
BEINGs are big and slow, but valuable for organizing knowledge in ways 
meaningful to how it will be used. In this proposed system, BEINGs will be one
-- but not the only -- 
internal mechanism for representing and manipulating knowledge.